package butines.game2.graph;

import static butines.game2.graph.GraphNode.INVALID_NODE_INDEX;

import java.util.ArrayList;
import java.util.List;

public class SparseGraph<Node extends GraphNode, Edge extends GraphEdge> {

    public class NodeVector extends ArrayList<Node> {
        private static final long serialVersionUID = 1L;
        
    }
    
    public class EdgeList extends ArrayList<Edge> {
        private static final long serialVersionUID = 1L;
        
    }
    
    public class EdgeListVector extends ArrayList<EdgeList> {
        private static final long serialVersionUID = 1L;
        
    }
    
    ///the nodes that comprise this graph
    private NodeVector nodes;

    //a vector of adjacency edge lists.
    // (each node index keys into the list of edges associated with that node)
    private EdgeListVector edges;
    
    //is this a directed graph?
    private boolean digraph;

    //the index of the next node to be added
    private int nextNodeIndex;
    
    public SparseGraph(boolean digraph) {
        this.digraph = digraph;
        nextNodeIndex = 0;
        nodes = new NodeVector();
        edges = new EdgeListVector();
    }
    
    //returns the number of active + inactive nodes present in the graph
    public int getNumNodes() {
        return nodes.size();
    }
    
    public Iterable<Node> getNodes() {
        return nodes;
    }

    public Iterable<Edge> getEdges(int idx) {
        if (idx == INVALID_NODE_INDEX) {
            return null;
        }
        return edges.get(idx);
    }

    //returns the number of active nodes present in the graph
    // (this method's performance can be improved greatly by caching the value)
    public int getNumActiveNodes() {
        int count = 0;
        for (int n = 0; n < nodes.size(); n++) {
            if (nodes.get(n).getIndex() != GraphNode.INVALID_NODE_INDEX) {
                count++;
            }
        }
        return count;
    }

    //returns the total number of edges present in the graph
    public int getNumEdges() {
        int count = 0;
        for (EdgeList edgeList : edges) {
            count += edgeList.size();
        }
        return count;
    }
    
    public int getNextFreeNodeIndex() {
        return nextNodeIndex;
    }
    
    //returns true if the graph is directed
    public boolean isDigraph() {
        return digraph;
    }
    
    //returns true if the graph contains no nodes
    public boolean isEmpty() {
        return nodes.isEmpty();
    }
    
    public void clear() {
        nextNodeIndex = 0;
        nodes.clear();
        edges.clear();
    }

    public void removeEdges() {
        for (EdgeList edgeList : this.edges) {
            edgeList.clear();
        }
    }
    
    //returns true if an edge is not already present in the graph. Used
    //when adding edges to make sure no duplicates are created.
    public boolean uniqueEdge(int from, int to) {
        for (Edge edge : edges.get(from)) {
            if (edge.getTo() == to) {
                return false;
            }
        }
        return true;
    }

    //iterates through all the edges in the graph and removes any that point
    //to an invalidated node
    private void cullInvalidEdges() {
        
        for (EdgeList edgeList : edges) {
            for (int i = edgeList.size() - 1; i >= 0; i--) {
                Edge edge = edgeList.get(i);
                if (edge.getTo() == INVALID_NODE_INDEX || edge.getFrom() == INVALID_NODE_INDEX) {
                    edgeList.remove(i);
                }
            }
        }
        
    }
    
    private void assertIndex(List<?> l, int idx, String str) {
        if (idx < 0 && idx >= l.size()) {
            throw new IllegalArgumentException(str);
        }
    }
    
    // returns the node at the given index
    public Node getNode(int idx) {
        assertIndex(nodes, idx, "Invalid index");
        return nodes.get(idx);
    }

    //const method for obtaining a reference to an edge
    public Edge getEdge(int from, int to) {
        assertIndex(nodes, from, "Invalid 'from' index");
        assertIndex(nodes, to, "Invalid 'to' index");
        
        for (Edge edge : edges.get(from)) {
            if (edge.getTo() == to) {
                return edge;
            }
        }
        
        return null;
    }
      
    //adds a node to the graph and returns its index
    public int addNode(Node node) {
        if (node.getIndex() < nodes.size()) {
            // make sure the client is not trying to add a node with the same ID as a currently active node
          
            nodes.set(node.getIndex(), node);
          
          return node.getIndex();
        } else {
            // make sure the new node has been indexed correctly
            if (node.getIndex() != nextNodeIndex) {
                throw new IllegalArgumentException("invalid index");
            }

            nodes.add(node);
            edges.add(new EdgeList());

            return nextNodeIndex++;
        }
    }

    //removes a node by setting its index to invalid_node_index
    public void removeNode(int node) {
        assertIndex(nodes, node, "Invalid index");

        //set this node's index to invalid_node_index
        nodes.get(node).setIndex(INVALID_NODE_INDEX);

        //if the graph is not directed remove all edges leading to this node and then
        //clear the edges leading from the node
        if (!digraph) {
            // visit each neighbour and erase any edges leading to this node

            for (Edge edge : edges.get(node)) {
                EdgeList edgeList = edges.get(edge.getTo());
                for (int i = edgeList.size() - 1; i >= 0; i--) {
                    Edge reverse = edgeList.get(i);
                    if (reverse.getTo() == node) {
                        edgeList.remove(i);
                        break;
                    }
                }
            }

            // finally, clear this node's edges
            edges.get(node).clear();
        } else {
            //if a digraph remove the edges the slow way
          cullInvalidEdges();
        }
    }

    @SuppressWarnings("unchecked")
    private Edge newInstance(Edge obj) {
        try {
            return (Edge) obj.getClass().newInstance();
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }
    
    //Use this to add an edge to the graph. The method will ensure that the
    //edge passed as a parameter is valid before adding it to the graph. If the
    //graph is a digraph then a similar edge connecting the nodes in the opposite
    //direction will be automatically added.
    public void addEdge(Edge edge) {
        
        //first make sure the from and to nodes exist within the graph 

        assertIndex(nodes, edge.getFrom(), "Invalid 'from' index");
        assertIndex(nodes, edge.getTo(), "Invalid 'to' index");
        
        //make sure both nodes are active before adding the edge
        if (nodes.get(edge.getTo()).getIndex() == INVALID_NODE_INDEX
                || nodes.get(edge.getFrom()).getIndex() == INVALID_NODE_INDEX) {
            return;
        }
        // add the edge, first making sure it is unique
        if (uniqueEdge(edge.getFrom(), edge.getTo())) {
            edges.get(edge.getFrom()).add(edge);
        }

        // if the graph is undirected we must add another connection in the opposite direction
        if (!digraph) {
            // check to make sure the edge is unique before adding
            if (uniqueEdge(edge.getTo(), edge.getFrom())) {
                Edge newEdge = newInstance(edge);
                newEdge.setTo(edge.getFrom());
                newEdge.setFrom(edge.getTo());
                edges.get(edge.getTo()).add(newEdge);
            }
        }
    }

    //removes the edge connecting from and to from the graph (if present). If
    //a digraph then the edge connecting the nodes in the opposite direction 
    //will also be removed.
    public void removeEdge(int from, int to) {
        
        assertIndex(nodes, from, "Invalid 'from' index");
        assertIndex(nodes, to, "Invalid 'to' index");
        
        EdgeList edgeList = null;
       if (digraph) {
            edgeList = edges.get(to);
            for (int i = edgeList.size() - 1; i >= 0; i--) {
                Edge edge = edgeList.get(i);
                if (edge.getFrom() == from) {
                    edgeList.remove(i);
                    break;
                }
            }
       }

       edgeList = edges.get(from);
       for (int i = edgeList.size() - 1; i >= 0; i--) {
           Edge edge = edgeList.get(i);
           if (edge.getTo() == to) {
               edgeList.remove(i);
               break;
          }
       }
      
    }

    //sets the cost of an edge
    public void setEdgeCost(int from, int to, float cost) {
        //make sure the nodes given are valid
        assertIndex(nodes, from, "Invalid index");

        //visit each neighbour and erase any edges leading to this node
        for (Edge edge : edges.get(from)) {
            if (edge.getTo() == to) {
                edge.setCost(cost);
                break;
            }
        }

    }

    //returns true if a node with the given index is present in the graph
    public boolean isNodePresent(int nd) {
        return nd >= 0 && nd < nodes.size()
            && nodes.get(nd).getIndex() == INVALID_NODE_INDEX;
    }

    //returns true if an edge connecting the nodes 'to' and 'from'
    //is present in the graph
    public boolean isEdgePresent(int from, int to) {
        if (isNodePresent(from) && isNodePresent(to)) {
            for (GraphEdge edge : edges.get(from)) {
                if (edge.getTo() == to) {
                    return true;
                }
            }
        }
        return false;
    }

}
